package xyz.sekai52799.answer.a801_a1000;

import java.util.HashMap;
import java.util.Map;

public class Question873 {
//    如果序列X_1, X_2, ..., X_n满足下列条件，就说它是斐波那契式的：
//
//    n >= 3
//    对于所有i + 2 <= n，都有X_i + X_{i+1} = X_{i+2}
//    给定一个严格递增的正整数数组形成序列 arr，找到 arr中最长的斐波那契式的子序列的长度。如果一个不存在，返回0 。
//
//            （回想一下，子序列是从原序列 arr中派生出来的，它从 arr中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。
//            例如，[3, 5, 8]是[3, 4, 5, 6, 7, 8]的一个子序列）
//
//
//
//    示例 1：
//
//    输入: arr = [1,2,3,4,5,6,7,8]
//    输出: 5
//    解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
//    示例2：
//
//    输入: arr = [1,3,7,11,12,14,18]
//    输出: 3
//    解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。
//
//
//    提示：
//
//            3 <= arr.length <= 1000
//            1 <= arr[i] < arr[i + 1] <= 10^9
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexMap.put(arr[i], i);
        }
        int maxCnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int f1 = i;
                int f2 = j;
                int cnt = 2;
                while (f2 < n && indexMap.containsKey(arr[f1] + arr[f2])) {
                    int temp = f2;
                    f2 = indexMap.get(arr[f1] + arr[f2]);
                    f1 = temp;
                    cnt++;
                }
                maxCnt = Math.max(maxCnt, cnt);
            }
        }
        return maxCnt == 2 ? 0 : maxCnt;
    }
}
